package com.berchen.算法.查找;

/**
 * 插值排序
 */
public class InsertpolationSearch {
    public static void main(String[] args) {
        int arr[] ={1,5,6,9,10,43,54};
        int i = insertpolation(arr,  54);
        System.out.println(i);
    }

    /**
     * 插值排序
     * @param arr
     * @param value
     * @return
     */
    public static int insertpolation(int [] arr,int value ){
        int left =0;
        int right=arr.length-1;
        int mid=0;
        while (true){

            // arr[0]>value||arr[arr.length-1]<value 保证mid不越界
            if(left>right||arr[0]>value||arr[arr.length-1]<value){
                return -1;
            }
            mid=left+(value-arr[left])*(right-left)/(arr[right]-arr[left]);
            if(value<arr[mid]){
                right=mid-1;
            }
            else if(value>arr[mid]){
                left=mid+1;
            }
            else {
                return mid;
            }
        }
    }
}
